package cn.yuemouren.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: Timi
 * @Description: 76. 最小覆盖子串
 *          滑动窗口问题
 * @Date: 2020/7/30 18:26
 */
public class Test_76 {

    public String minWindow(String s, String t) {

        Map<Character,Integer> sMap = new HashMap<>();
        Map<Character,Integer> tMap = new HashMap<>();
        for (int i = 0; i < t.length(); i++){
            tMap.put(t.charAt(i),tMap.getOrDefault(t.charAt(i),0) + 1);
        }

        int left = 0,right = 0,count = 0,tLen = t.length();
        int start = 0,len = Integer.MAX_VALUE;

        while (right < s.length()){

            char c = s.charAt(right);
            sMap.put(c,sMap.getOrDefault(c,0) + 1);
            if(tMap.containsKey(c) && sMap.get(c) <= tMap.get(c)){
                count++;
            }

            while(tLen == count){
                //更新最小覆盖子串
                if((right - left) < len){
                    start = left;
                    len = right - left + 1;
                }
                //移出窗口的元素
                char c1 = s.charAt(left);
                if(tMap.containsKey(c1) && sMap.get(c1) <= tMap.get(c1)){
                    count--;
                }
                sMap.put(c1,sMap.getOrDefault(c1,1) - 1);
                //左移窗口
                left++;
            }
            right++;
        }
        if(len == Integer.MAX_VALUE){
            return "";
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start,start + len);
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(new Test_76().minWindow(s,t));
    }
}
